{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f6ee8a25-1af6-49df-a05e-6092e28e7326",
   "metadata": {},
   "source": [
    "# Bernstein-Vazirani Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22ec3e91-cc89-43be-88d0-1a36639e5e4e",
   "metadata": {},
   "source": [
    "The Bernstein-Vazirani (BV) algorithm [[1](#BVWiki)], named after Ethan Bernstein and Umesh Vazirani, is a basic quantum algorithm. It gives a linear speed-up with respect to its classical counterpart, in the oracle complexity setting.\n",
    "\n",
    "The algorithm treats the following problem:\n",
    "\n",
    "* **Input:** A Boolean function $f: \\{0,1\\}^n \\rightarrow \\{0,1\\}$ defined as\n",
    "$$\n",
    "f(x)\\equiv (x\\cdot a) \\,\\,\\mod 2,\n",
    "$$\n",
    "where the $ \\cdot$ refers to a bitwise dot operation, and $a$ is some binary string of length $n$.\n",
    "\n",
    "* **Output:** Returns the secret string $a$ with the minimal inquries of the function.\n",
    "\n",
    "\n",
    "Comments:\n",
    "* This problem is a special case of the [hidden-shift problem](https://github.com/Classiq/classiq-library/blob/main/algorithms/algebraic/hidden_shift/hidden_shift.ipynb), where the goal is to find a secret string satisfing $f(x)=f(x\\oplus a)$, with $\\oplus$ indicating bitwise addition.\n",
    "* The problem can be considered as a restricted version of the [Duetsch-Jozsa algorithm](https://github.com/Classiq/classiq-library/blob/main/algorithms/deutsch_jozsa/deutsch_jozsa.ipynb). In particular, the functional quantum circuit is identical for both problems.\n",
    "\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7203db9-e55c-425c-af47-ced473d0b139",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "Problem Hardness: Classically, the minimal inquiries of the function $f$ for determining the secret string is $n$: $f$ is called with the strings \n",
    "$$\n",
    "\\begin{eqnarray}\n",
    "f(100\\dots0) &=& a_0, \\\\\n",
    "f(010\\dots0) &=& a_1, \\\\\n",
    "\\vdots\\\\\n",
    "f(00\\dots01)&=& a_{n-1},\n",
    "\\end{eqnarray}\n",
    "$$\n",
    "which reveals the secret string, one bit at a time. **The BV algorithm finds the secret string using one function call (oracle inquiry); thus, providing a linear speed-up with respect to the classical solution.**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77cf2c97-2d0e-44cf-8192-4f5d2e2f87de",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"https://docs.classiq.io/resources/bernstein_vazirani_algorithm.png\" style=\"width:100%\">\n",
    "<figcaption align = \"middle\"> Figure 1. The Bernstein-Vazirani algorithm comprises three quantum blocks. The main part of the algorithm\n",
    "is the implementation of the Bernstein-Vazirani predicate $f(x)\\equiv (x\\cdot a) \\mod 2$. </figcaption>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58a12dc6-d6b8-4837-87dd-5fae9fc1d97b",
   "metadata": {},
   "source": [
    "## How to Build the Algorithm with Classiq\n",
    "\n",
    "The BV algorithm contains three function blocks: an oracle for the predicate $f$, \"sandwiched\" between two Hadamard transforms. The resulting state corresponds to the secret string. The full [mathematical derivation](#Technical-Notes) is given at the end of this notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93c8fae1-7e6d-40ec-96f5-7fc26dde3c38",
   "metadata": {},
   "source": [
    "### Implementing the BV Predicate\n",
    "\n",
    "A simple quantum implementation of the binary function $f(x)$ is by applying a series of controlled-X operations: starting with the state $|f\\rangle=|0\\rangle$, we apply an X gate on it, controlled on the $|x_i\\rangle$ state, for all $i$ such that $a_i=1$:\n",
    "$$\n",
    " |x_0\\dots x_{n-1}\\rangle |0\\rangle_f \\rightarrow \\Pi_{i: a_i=1} {\\rm CX}(x_i,f)  |x_0\\dots x_{n-1}\\rangle |0\\rangle_f = |x_0\\dots x_{n-1}\\rangle X^{a\\cdot x}|0\\rangle_f=|x_0\\dots x_{n-1}\\rangle |a\\cdot x \\left(\\text{ mod } 2\\right)\\rangle_f.\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1de041eb-4f59-48c0-a181-6858b330e627",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:53:58.499882Z",
     "iopub.status.busy": "2024-05-07T14:53:58.499417Z",
     "iopub.status.idle": "2024-05-07T14:54:01.333608Z",
     "shell.execute_reply": "2024-05-07T14:54:01.332741Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import CX, IDENTITY, CInt, QArray, QBit, allocate, if_, qfunc, repeat\n",
    "from classiq.qmod.symbolic import floor\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def bv_predicate(a: CInt, x: QArray, res: QBit):\n",
    "\n",
    "    repeat(\n",
    "        x.len,\n",
    "        lambda i: if_(\n",
    "            floor(a / 2**i) % 2 == 1, lambda: CX(x[i], res), lambda: IDENTITY(res)\n",
    "        ),\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6acafe39-631c-44d9-ae60-b21dc253d5ee",
   "metadata": {},
   "source": [
    "Figure 1 shows an example for such implementation, for $a=01101$ and $n=5$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a39a3a0-1c18-4173-90a0-17c650012d2c",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"https://docs.classiq.io/resources/bernstein-vazirani_predicate.png\" style=\"width:80%\">\n",
    "<figcaption align = \"middle\"> Figure 1. The Bernstein Vazirani Predicate $f(x)$ for a secret string $a=01101$, on $n$ qubits.\n",
    "The quantum variable $x$ is stored on the 5 upper qubits and the resulting value of $f$ is on the lower-most qubit.</figcaption>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc0b85cf-682e-44fb-b6da-9a65723ac8a6",
   "metadata": {},
   "source": [
    "### Implementing the BV Quantum Function\n",
    "\n",
    "The quantum part of the BV algorithm is essentially identical to the Deutch-Jozsa one, see `deutsch_jozsa` function in [Deutsch-Jozsa notebook](https://github.com/Classiq/classiq-library/blob/main/algorithms/deutsch_jozsa/deutsch_jozsa.ipynb). However, in contrast to the latter, the predicate function implementation is fixed, depending solely on the secret string $a$. Hereafter we refer to the secret string as a secret integer, defined as an integer argument for the `bv_function`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "c6940ec0-8342-4fba-b827-46f3883b3ac3",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:54:01.339860Z",
     "iopub.status.busy": "2024-05-07T14:54:01.338317Z",
     "iopub.status.idle": "2024-05-07T14:54:01.354674Z",
     "shell.execute_reply": "2024-05-07T14:54:01.353838Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import H, X, hadamard_transform, within_apply\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def bv_function(a: CInt, x: QArray):\n",
    "\n",
    "    aux = QBit(\"aux\")\n",
    "    hadamard_transform(x)\n",
    "    within_apply(\n",
    "        lambda: (allocate(1, aux), X(aux), H(aux)), lambda: bv_predicate(a, x, aux)\n",
    "    )\n",
    "    hadamard_transform(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "134ef74c-180b-4b60-9b35-c64ee626c2db",
   "metadata": {},
   "source": [
    "## An Example on 5 Qbits\n",
    "\n",
    "We construct a model for a specific example, setting the secret integer to $a=13$ and $n=5$.\n",
    "\n",
    "We can essentially set the number of shots to 1. This is because that under the assumption of noiseless execution, the resulting state is just the secret integer (see last equation Eq. ([1](#mjx-eqn-1)) below). In particular, the idea of using solely 1 shot was used to demonstrate algorithmic speedup in Ref. [[2](#ssBV)], where the authors considered a modified version of the BV algorithm in which the secret integer changes after every inquiry.\n",
    "\n",
    "In our example, we take `num_shots=1000` to highlight the fact that the resulting state is purely the secret string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "31536bc7-2fb8-4ad8-84fe-4f5b99d812aa",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:54:01.360595Z",
     "iopub.status.busy": "2024-05-07T14:54:01.359290Z",
     "iopub.status.idle": "2024-05-07T14:54:03.926637Z",
     "shell.execute_reply": "2024-05-07T14:54:03.926010Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "from classiq import Output, create_model, synthesize\n",
    "from classiq.execution import ExecutionPreferences\n",
    "\n",
    "SECRET_INT = 13\n",
    "STRING_LENGTH = 5\n",
    "NUM_SHOTS = 1000\n",
    "assert (\n",
    "    np.floor(np.log2(SECRET_INT) + 1) <= STRING_LENGTH\n",
    "), \"The STRING_LENGTH cannot be smaller than secret string length\"\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def main(x: Output[QArray]):\n",
    "    allocate(STRING_LENGTH, x)\n",
    "    bv_function(SECRET_INT, x)\n",
    "\n",
    "\n",
    "qmod = create_model(\n",
    "    main, execution_preferences=ExecutionPreferences(num_shots=NUM_SHOTS)\n",
    ")\n",
    "qprog = synthesize(qmod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "3de671c1-e886-4e4c-920e-dc1e53008aa9",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:54:03.929511Z",
     "iopub.status.busy": "2024-05-07T14:54:03.928981Z",
     "iopub.status.idle": "2024-05-07T14:54:03.937758Z",
     "shell.execute_reply": "2024-05-07T14:54:03.937153Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import write_qmod\n",
    "\n",
    "write_qmod(qmod, \"bernstein_vazirani_example\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e210edf-f2ce-478a-9118-655d1d64f0cc",
   "metadata": {},
   "source": [
    "We can now visualize the circuit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "5aed0709-6746-4e30-9237-e01444d2cb43",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:54:03.940015Z",
     "iopub.status.busy": "2024-05-07T14:54:03.939820Z",
     "iopub.status.idle": "2024-05-07T14:54:04.002372Z",
     "shell.execute_reply": "2024-05-07T14:54:04.001648Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/aab784a3-ef20-450a-8001-b755f81df876?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "from classiq import show\n",
    "\n",
    "show(qprog)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13b5c366-c2d9-4ee3-9f33-c5d033d34897",
   "metadata": {},
   "source": [
    "We execute and extract the result:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "adb27aa5-17e8-47c0-a1c5-5851c4d9aa40",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:54:04.005027Z",
     "iopub.status.busy": "2024-05-07T14:54:04.004688Z",
     "iopub.status.idle": "2024-05-07T14:54:05.480022Z",
     "shell.execute_reply": "2024-05-07T14:54:05.479244Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import execute\n",
    "\n",
    "res = execute(qprog).result()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "56db1ac8-6cc1-45a9-a97b-ab00c3138842",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:54:05.485073Z",
     "iopub.status.busy": "2024-05-07T14:54:05.483852Z",
     "iopub.status.idle": "2024-05-07T14:54:05.492546Z",
     "shell.execute_reply": "2024-05-07T14:54:05.491843Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The secret integer is: 13.0\n",
      "The probability for measuring the secret integer is: 1.0\n"
     ]
    }
   ],
   "source": [
    "secret_integer_q = res[0].value.parsed_counts[0].state[\"x\"]\n",
    "print(\"The secret integer is:\", secret_integer_q)\n",
    "print(\n",
    "    \"The probability for measuring the secret integer is:\",\n",
    "    res[0].value.parsed_counts[0].shots / NUM_SHOTS,\n",
    ")\n",
    "\n",
    "assert int(secret_integer_q) == SECRET_INT"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1ad526a-6930-4d80-8436-978493da4a33",
   "metadata": {},
   "source": [
    "## Technical Notes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8c52c24-f49b-424a-bd42-c881146b5921",
   "metadata": {},
   "source": [
    "A brief summary of the linear algebra behind the Bernstein-Vazirani algorithm. The first Hadamard transformation generates an equal super-position over all the standard basis elements:\n",
    "$$\n",
    "|0\\rangle_n \\xrightarrow[H^{\\otimes n}]{} \\frac{1}{2^{n/2}}\\sum^{2^n-1}_{j=0}|j\\rangle_n.\n",
    "$$\n",
    "The oracle gets the boolean Bernstein-Vazirani predicate and adds an $e^{\\pi i}=-1$ phase to all states for which the function returns True:\n",
    "$$\n",
    "\\frac{1}{2^{n/2}}\\sum^{2^n-1}_{j=0}|j\\rangle_n \\xrightarrow[\\text{Oracle}(f(j))]{}\\frac{1}{2^{n/2}}\\sum^{2^n-1}_{j=0}(-1)^{a\\cdot j}|j\\rangle_n.\n",
    "$$\n",
    "Finally, application of the Hadamard transform, which can be written as $H^{\\otimes n}\\equiv \\frac{1}{2^{n/2}}\\sum^{2^n-1}_{k,l=0}(-1)^{k\\cdot l} |k\\rangle \\langle l| $, gives\n",
    "$$\n",
    "\\frac{1}{2^{n/2}}\\sum^{2^n-1}_{j=0}(-1)^{a\\cdot j}|j\\rangle  \\xrightarrow[H^{\\otimes n}]{} \n",
    "\\sum^{2^n-1}_{k=0} \\left(\\frac{1}{2^{n}}\\sum^{2^n-1}_{j=0}(-1)^{j\\cdot \\left(k\\oplus a \\right)} \\right) |k\\rangle.\n",
    "$$\n",
    "The final expression represents a super-position over all basis states $|k\\rangle$; however, one can verify that the amplitude of the state $|k\\rangle=|a\\rangle$ is simply 1, as $a\\oplus a =0$:\n",
    "$$\n",
    "\\begin{equation*}\n",
    "\\left(\\frac{1}{2^{n}}\\sum^{2^n-1}_{j=0}1 \\right) |a\\rangle  + \\sum^{2^n-1}_{k\\neq a} 0 |k\\rangle = |a\\rangle.\n",
    "\\tag{1}\n",
    "\\end{equation*}\n",
    "$$\n",
    "Therefore, the final state is simply the secret string."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55c15865-753c-473f-8e4d-84aa2f94ce12",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "<a id='BVWiki'>[1]</a>: [Bernstein–Vazirani (Wikipedia)](https://en.wikipedia.org/wiki/Bernstein%E2%80%93Vazirani_algorithm)\n",
    "\n",
    "<a id='ssBV'>[2]</a>: [Pokharel B., and Daniel A. L. \"Demonstration of algorithmic quantum speedup.\" Physical Review Letters 130, 210602 (2023)](https://arxiv.org/abs/2207.07647)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5998a341-60fb-4db0-b325-29a9235fcc56",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
